《剑指offer》 29. 顺时针打印矩阵

note: 虽然是简单题,但是挺麻烦,尤其是在(好久)没做过的情况下,建议记住方法二的第二种写法,更简洁易懂一点。

题目描述

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1:

1
2
输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]

示例 2:

1
2
输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]

限制:

1
2
0 <= matrix.length <= 100
0 <= matrix[i].length <= 100

方法一 模拟

思路

通过方向数组模拟遍历路径,以便进行顺时针旋转。同时搭配一个标识是否访问过的数组,防止重复访问。

首先是向右、向下、向左和向上的方向数组:

static constexpr int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 方向数组

使用方向索引directionIndex来决定选用那个方向数组。

然后引入理论下标nextRownextColumn,来计算方向不改变时,下一个要访问的元素的下标。

判断理论下标是否合法,不合法的情况有两个,其一是数组越界,其二是访问的元素已经访问过了。

当理论下标不合法时,变换方向索引到顺时针的下个方向。

然后更新下标为真实的合法下标。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
private:
static constexpr int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 方向数组
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
// 超出情况
if (matrix.size() == 0 || matrix[0].size() == 0) {
return {};
}

int rows = matrix.size(), columns = matrix[0].size();
vector<vector<bool>> visited(rows, vector<bool>(columns)); // 标识数组
int total = rows * columns;
vector<int> order(total);

int row = 0, column = 0;
int directionIndex = 0; // 方向索引
for (int i = 0; i < total; i++) { // 所有元素都访问到
order[i] = matrix[row][column];
visited[row][column] = true; // 标记标识数组
// 下一个访问的数组元素下标理论值
int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
// 理论值是否不合法,不合法顺时针转换方向
if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
directionIndex = (directionIndex + 1) % 4;
}
// 下标的真实变换
row += directions[directionIndex][0];
column += directions[directionIndex][1];
}
return order;
}
};

复杂度分析

  • 时间复杂度$O(mn)$。要遍历所有的元素,m n分别为矩阵的长和宽
  • 空间复杂度$O(mn)$。需要一个和矩阵相同大小的二维数组作为标记数组。

方法二 按层遍历

思路

方法一的思路是矩阵不变,标记已访问的元素避免重复访问。

事实上,我们也可以不断改变矩阵的边界,达到一层层缩小矩阵的边界的效果,按层遍历,从而可以得到顺时针遍历同样的效果。

我们用四个变量l r t b代表当前层的矩阵的左右上下边界

在左边界大于右边界、上边界大于下边界之前,我们重复四个步骤

  • 从左到右访问上边界那一排元素
  • 从上到下访问右边界那一列元素
  • 如果左上边界都小于右下边界,那么我们
    • 从右到左访问下边界这一排元素
    • 从下到上访问左边界这一排元素
  • 更改边界,左边界上边界自增,右边界下边界自减。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if(matrix.size()==0 || matrix[0].size()==0){
return {};
}

int m = matrix.size(),n=matrix[0].size();

int l=0,r=n-1,t=0,b=m-1;
vector<int> ans;
while(l<=r && t<=b){
for(int i=l;i<=r;i++){
ans.push_back(matrix[t][i]);
}
for(int i=t+1;i<=b;i++){
ans.push_back(matrix[i][r]);
}
if (l < r && t < b){
for(int i=r-1;i>l;i--){
ans.push_back(matrix[b][i]);
}
for(int i=b;i>t;i--){
ans.push_back(matrix[i][l]);
}
}
l++;
r--;
t++;
b--;
}
return ans;
}
};

如果较难理解,还有一种写法,即在每排每列访问完后,立刻进行边界的缩小,并判断是否合法,如果不合法则说明已经遍历完毕,可以直接结束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution 
{
public:
vector<int> spiralOrder(vector<vector<int>>& matrix)
{
if (matrix.empty()) return {};
vector<int> res;
int l = 0; //左边界
int r = matrix[0].size() - 1; //右边界
int t = 0; //上边界
int b = matrix.size() - 1; //下边界
while (true)
{
//left -> right
for (int i = l; i <= r; i++) res.push_back(matrix[t][i]);
if (++t > b) break;
//top -> bottom
for (int i = t; i <= b; i++) res.push_back(matrix[i][r]);
if (--r < l) break;
//right -> left
for (int i = r; i >= l; i--) res.push_back(matrix[b][i]);
if (--b < t) break;
//bottom -> top
for (int i = b; i >= t; i--) res.push_back(matrix[i][l]);
if (++l > r) break;
}
return res;
}
};

复杂度分析

  • 时间复杂度:$O(mn)$。要访问矩阵种所有的元素
  • 空间复杂度:$O(1)$。不需要标记数组。